package 链表;

import java.util.ArrayList;
import java.util.List;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/21 17:33
 */
public class leetcode143重排链表 {




    /*
     直接使用 数组， 进行一个 暴力的模拟，
     但是要注意 一些细节 在里面！
     时空复杂度O（N）
     */
    public  void solution(ListNode node){
        List<ListNode> list = new ArrayList<>();
        while(node != null){
            list.add(node);
            node = node.next;
        }
        ListNode sentinel = new ListNode(0);
        int l,r;
        for( l = 0, r = list.size() - 1;l < r;l++,r-- ){
            sentinel.next = list.get(l);
            list.get(l).next = list.get(r);
            sentinel = list.get(r);
        }
        sentinel.next = list.get(l);
        list.get(l).next = null;
//        sentinel.next = null;
//        sentinel = list.get(0);
//        StringBuilder sb = new StringBuilder();
//        sb.append("[");
//        while(sentinel .next != null){
//            sb.append(sentinel.val);
//            sb.append(",");
//            sentinel = sentinel.next;
//        }
//
//        sb.append(sentinel.val);
//        sb.append("]");
//        System.out.println(sb.toString());
    }




   /*
   **这个题是真的 有意思!**

    直接在 原链表上， 进行一个 修改！
    基本思路，
    1. 先使用 快慢指针 把链表分成两部分
    2. 再将 分割的后面的 链表进行一个 反转
    3. 然后将反转的链表与 前一个链表进行一个 合并就行了！
    时间复杂度 O(N) 空间复杂度 O（1）
    */
    public void solutionOne(ListNode head){
        ListNode slow = head,fast = head;
        // 1. 找到 链表的中点
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //  2. 将 以 slow.next 为头的链表进行一个反转 , 并且 注意一下, 反转执行之后, pre 就是 反转后链表的头部!
        ListNode cur = slow.next,pre = null;
        slow.next = null;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }

        // 3. 将两个链表进行合并!
        slow = head;
        ListNode node = pre;
        while(node != null){
            ListNode temp = node.next;
            node.next = slow.next;
            slow.next = node;
            slow = node.next;
            node = temp;
        }

    }

    /*
     递归式的 阴间 写法!
     也许可以借鉴 一手!
     */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return ;
        ListNode p = head;
        while (p.next.next != null) {
            p = p.next;
        }
        ListNode insertNode = p.next;
        p.next = null;
        insertNode.next = head.next;
        head.next = insertNode;
        reorderList(insertNode.next);
    }



    class ListNode {
        int val;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }

    }

}
